@Part[List, Root = "CLM.MSS"]
@Comment{Chapter of Common Lisp Manual.  Copyright 1984 Guy L. Steele Jr.⎇

@MyChapter[Lists]

A @Def[cons], or dotted pair, is a compound data object having two components
called the @Def[car] and @Def[cdr].  Each component may be any @xlisp object.
A @Def[list] is a chain of conses
linked by @i[cdr] fields; the chain is terminated by some atom
(a non-cons object).
An ordinary list is terminated by @nil, the empty list
(also written @empty).
A list whose @i[cdr] chain is terminated by some non-@nil atom is called
a @Def[dotted list].
@Seealso[P {list⎇, S {dotted list⎇]

The recommended predicate for testing for the end of a list is @Funref[endp].

@Section[Conses]

These are the basic operations on conses viewed as pairs rather than
as the constituents of a list.

@Defun[Fun {car⎇, Args {@i[list]⎇]
This returns the @i[car] of @i[list], which must be a cons or @empty;
that is, @i[list] must satisfy the predicate @Funref[listp].
By definition, the @i[car] of @empty is @empty.
If the cons is regarded as the first cons of a list, then @f[car]
returns the first element of the list.
For example:
@lisp
(car '(a b c)) @EV a
@Endlisp
See @Funref[first].
The @i[car] of a cons may be altered by using @Funref[rplaca] or @Macref[setf].
@Enddefun

@Defun[Fun {cdr⎇, Args {@i[list]⎇]
This returns the @i[cdr] of @i[list], which must be a cons or @empty;
that is, @i[list] must satisfy the predicate @Funref[listp].
By definition, the @i[cdr] of @empty is @empty.
If the cons is regarded as the first cons of a list, then @f[cdr]
returns the rest of the list, which is a list with all elements
but the first of the original list.
For example:
@lisp
(cdr '(a b c)) @EV (b c)
@Endlisp
See @Funref[rest].
The @i[cdr] of a cons may be altered by using @Funref[rplacd] or @Macref[setf].
@Enddefun

@Defun[Fun {caar⎇, Args {@i[list]⎇]
@Defun1[Fun {cadr⎇, Args {@i[list]⎇]
@Defun1[Fun {cdar⎇, Args {@i[list]⎇]
@Defun1[Fun {cddr⎇, Args {@i[list]⎇]
@Defun1[Fun {caaar⎇, Args {@i[list]⎇]
@Defun1[Fun {caadr⎇, Args {@i[list]⎇]
@Defun1[Fun {cadar⎇, Args {@i[list]⎇]
@Defun1[Fun {caddr⎇, Args {@i[list]⎇]
@Defun1[Fun {cdaar⎇, Args {@i[list]⎇]
@Defun1[Fun {cdadr⎇, Args {@i[list]⎇]
@Defun1[Fun {cddar⎇, Args {@i[list]⎇]
@Defun1[Fun {cdddr⎇, Args {@i[list]⎇]
@Defun1[Fun {caaaar⎇, Args {@i[list]⎇]
@Defun1[Fun {caaadr⎇, Args {@i[list]⎇]
@Defun1[Fun {caadar⎇, Args {@i[list]⎇]
@Defun1[Fun {caaddr⎇, Args {@i[list]⎇]
@Defun1[Fun {cadaar⎇, Args {@i[list]⎇]
@Defun1[Fun {cadadr⎇, Args {@i[list]⎇]
@Defun1[Fun {caddar⎇, Args {@i[list]⎇]
@Defun1[Fun {cadddr⎇, Args {@i[list]⎇]
@Defun1[Fun {cdaaar⎇, Args {@i[list]⎇]
@Defun1[Fun {cdaadr⎇, Args {@i[list]⎇]
@Defun1[Fun {cdadar⎇, Args {@i[list]⎇]
@Defun1[Fun {cdaddr⎇, Args {@i[list]⎇]
@Defun1[Fun {cddaar⎇, Args {@i[list]⎇]
@Defun1[Fun {cddadr⎇, Args {@i[list]⎇]
@Defun1[Fun {cdddar⎇, Args {@i[list]⎇]
@Defun1[Fun {cddddr⎇, Args {@i[list]⎇]
All of the compositions of up to four @f[car] and @f[cdr] operations
are defined as separate @clisp functions.
The names of these functions begin with @f[c] and end with @f[r],
and in between is a sequence of @f[a] and @f[d] letters
corresponding to
the composition performed by the function. 
For example:
@lisp
(cddadr x) @r[is the same as] (cdr (cdr (car (cdr x))))
@Endlisp
If the argument is regarded as a list, then @f[cadr] returns
the second element of the list, @f[caddr] the third, and @f[cadddr]
the fourth.  If the first element of a list is a list, then
@f[caar] is the first element of the sublist, @f[cdar] is the
rest of that sublist, and @f[cadar] is the second element of the sublist,
and so on.

As a matter of style, it is often preferable to define a function or
macro to access part of a complicated data structure, rather than to use
a long @f[car]/@f[cdr] string.  For example, one might define
a macro to extract the list of parameter variables from a lambda-expression:
@Lisp
(defmacro lambda-vars (lambda-exp) `(cadr ,lambda-exp))
@Endlisp
and then use @f[lambda-vars] for this purpose instead of @f[cadr].
See also @Macref[defstruct], which will automatically define
new record data types and access functions for instances of them.

Any of these functions may be used to specify a @i[place] for @Macref[setf].
@Enddefun
	
@Defun[Fun {cons⎇, Args {@i[x] @i[y]⎇]
@f[cons] is the primitive function to create a new @i[cons] whose
@i[car] is @i[x] and whose @i[cdr] is @i[y].
For example:
@lisp
(cons 'a 'b) @EV (a . b)
(cons 'a (cons 'b (cons 'c '@empty))) @EV (a b c)
(cons 'a '(b c d)) @EV (a b c d)
@Endlisp
@f[cons] may be thought of as creating a @i[cons], or as adding a new element
to the front of a list.
@Enddefun

@Defun[Fun {tree-equal⎇, Args {@i[x] @i[y]⎇, Keys {[test][test-not]⎇]
This is a predicate that is true if @i[x] and @i[y] are
isomorphic trees with identical leaves, that is, if @i[x] and @i[y]
are atoms that satisfy the test (by default @f[eql]),
or if they are both conses and their @i[car]'s are @f[tree-equal]
and their @i[cdr]'s are @f[tree-equal].
Thus @f[tree-equal] recursively compares conses (but not any other objects
that have components).  See @Funref[equal], which does recursively
compare certain other structured objects, such as strings.
@Enddefun

@Section[Lists]

The following functions perform various non-destructive operations
on lists.

@Defun[Fun {endp⎇, Args {@i[object]⎇]
The predicate @f[endp] is the recommended way to test for the end
of a list.  It is false of conses, true of @nil, and an error for
all other arguments.
@Implementation{Implementations are encouraged to signal an
error, especially in the interpreter, for a non-list argument.
The @f[endp] function is defined so as to allow compiled code
to perform simply an atom check or a null check if speed is more
important than safety.⎇
@Enddefun

@Defun[Fun {list-length⎇, Args {@i[list]⎇]
@f[list-length] returns, as an integer, the length of @i[list].
@f[list-length] differs from @Funref[length] when the @i[list] is
circular; @f[length] may fail to return, whereas @f[list-length]
will return @nil.
For example:
@lisp
(list-length '@empty) @EV 0
(list-length '(a b c d)) @EV 4
(list-length '(a (b c) d)) @EV 3
(let ((x (list 'a b c)))
  (rplacd (last x) x)
  (list-length x)) @EV @nil
@Endlisp
@f[list-length] could be implemented as follows:
@Lisp
(defun list-length (x)
  (do ((n 0 (+ n 2))		;Counter.
       (fast x (cddr fast))	;Fast pointer: leaps by 2.
       (slow x (cdr slow)))	;Slow pointer: leaps by 1.
      (nil)
    ;; If fast pointer hits the end, return the count.
    (when (endp fast) (return n))
    (when (endp (cdr fast)) (return (+ n 1)))
    ;; If fast pointer eventually equals slow pointer,
    ;;  then we must be stuck in a circular list.
    ;; (A deeper property is the converse: if we are
    ;;  stuck in a circular list, then eventually the
    ;;  fast pointer will equal the slow pointer.
    ;;  That fact justifies this implementation.)
    (when (and (eq fast slow) (> n 0)) (return nil))))
@Endlisp
See @Funref[length], which will return the length of any sequence.
@Enddefun

@Defun[Fun {nth⎇, Args {@i[n] @i[list]⎇]
@f[(nth @i[n] @i[list])] returns the @i[n]th element of @i[list], where
the @i[car] of the list is the ``zeroth'' element.
The argument @i[n] must be a non-negative integer.
If the length of the list is not greater than @i[n], then the result
is @empty, that is, @false.
(This is consistent with the idea that the @i[car] and @i[cdr]
of @empty are each @empty.)
For example:
@lisp
(nth 0 '(foo bar gack)) @EV foo
(nth 1 '(foo bar gack)) @EV bar
(nth 3 '(foo bar gack)) @EV @empty
@Endlisp
@Incompatibility{This is not
the same as the @Interlisp function called @f[nth],
which is similar to but not exactly the same as the @clisp function
@f[nthcdr].  This definition of @f[nth] is compatible
with @lmlisp and @newlisp.
Also, some people have used macros and functions called @f[nth] of their own in
their old @Maclisp programs, which may not work the same way.⎇

@f[nth] may be used to specify a @i[place] to @Macref[setf];
when @f[nth] is used in this way, the argument @i[n] must be less
than the length of the @i[list].

Note that the arguments to @f[nth] are reversed from the order
used by most other sequence selector functions such as @Funref[elt].
@Enddefun


@Defun[Fun {first⎇, Args {@i[list]⎇]
@Defun1[Fun {second⎇, Args {@i[list]⎇]
@Defun1[Fun {third⎇, Args {@i[list]⎇]
@Defun1[Fun {fourth⎇, Args {@i[list]⎇]
@Defun1[Fun {fifth⎇, Args {@i[list]⎇]
@Defun1[Fun {sixth⎇, Args {@i[list]⎇]
@Defun1[Fun {seventh⎇, Args {@i[list]⎇]
@Defun1[Fun {eighth⎇, Args {@i[list]⎇]
@Defun1[Fun {ninth⎇, Args {@i[list]⎇]
@Defun1[Fun {tenth⎇, Args {@i[list]⎇]
These functions are sometimes convenient for accessing particular
elements of a list.  @f[first] is the same as @Funref[car],
@f[second] is the same as @f[cadr], @f[third] is the
same as @f[caddr], and so on.
Note that the ordinal numbering used here is one-origin,
as opposed to the zero-origin numbering used by @Funref[nth]:
@lisp
(fifth x) @EQ (nth 4 x)
@Endlisp

@Macref[setf] may be used with each of these functions to store
into the indicated position of a list.
@Enddefun

@Defun[Fun {rest⎇, Args {@i[list]⎇]
@f[rest] means the same as @f[cdr] but mnemonically complements @f[first].
@Macref[setf] may be used with @f[rest] to replace the @i[cdr] of a list
with a new value.
@Enddefun

@Defun[Fun {nthcdr⎇, Args {@i[n] @i[list]⎇]
@f[(nthcdr @i[n] @i[list])] performs the @f[cdr] operation @i[n] times
on @i[list], and returns the result.
For example:
@lisp
(nthcdr 0 '(a b c)) @EV (a b c)
(nthcdr 2 '(a b c)) @EV (c)
(nthcdr 4 '(a b c)) @EV @empty
@Endlisp
In other words, it returns the @i[n]th @i[cdr] of the list.
@Incompatibility{This is similar to the @Interlisp function @f[nth],
except that the @Interlisp function is one-based instead of zero-based.⎇
@Lisp
(car (nthcdr n x)) @EQ (nth n x)
@Endlisp
@Enddefun

@Defun[Fun {last⎇, Args {@i[list]⎇]
@f[last] returns the last cons (@i[not] the last element!) of @i[list].
If @i[list] is @empty, it returns @empty.
For example:
@lisp
(setq x '(a b c d))
(last x) @EV (d)
(rplacd (last x) '(e f))
x @EV '(a b c d e f)
(last '(a b c . d)) @EV (c . d)
@Endlisp
@Enddefun

@Defun[Fun {list⎇, Args {@rest @i[args]⎇]
@f[list] constructs and returns a list of its arguments.
For example:
@lisp
(list 3 4 'a (car '(b . c)) (+ 6 -2)) @EV (3 4 a b 4)
@Endlisp
@Enddefun

@Defun[Fun {list*⎇, Args {@i[arg] @rest @i[others]⎇]
@f[list*] is like @f[list] except that the last @i[cons]
of the constructed list is ``dotted.''  The last argument to @f[list*]
is used as the @i[cdr] of the last cons constructed;
this need not be an atom.  If it is not an atom,
then the effect is to add several new elements to the front of a list.
For example:
@lisp
(list* 'a 'b 'c 'd) @EV (a b c . d)
@r[This is like]
(cons 'a (cons 'b (cons 'c 'd)))
@r[Also:]
(list* 'a 'b 'c '(d e f)) @EV (a b c d e f)
(list* x) @EQ x
@Endlisp
@Enddefun

@Defun[Fun {make-list⎇, Args {@i[size]⎇, Keys {[initial-element]⎇]
This creates and returns a list containing @i[size] elements, each
of which is initialized to the @Kwd[initial-element]
argument (which defaults to @false).
@i[size] should be a non-negative integer.
For example:
@lisp
(make-list 5) @EV (@false @false @false @false @false)
(make-list 3 @Kwd[initial-element] 'rah) @EV (rah rah rah)
@Endlisp
@Enddefun

@Defun[Fun {append⎇, Args {@rest @i[lists]⎇]
The arguments to @f[append] are lists.  The result is a list that is the
concatenation of the arguments.
The arguments are not destroyed.
For example:
@lisp
(append '(a b c) '(d e f) '@empty '(g)) @EV (a b c d e f g)
@Endlisp
Note that @f[append] copies the top-level list structure of each of its
arguments @i[except] the last.
The function @Funref[concatenate] can perform a similar operation, but always
copies all its arguments.  See also @Funref[nconc], which is like @f[append]
but destroys all arguments but the last.

The last argument actually need not be a list but may be any @xlisp object,
which becomes the tail end of the constructed list.
For example, @f[(append '(a b c) 'd)] @EV @f[(a b c . d)].

@f[(append @i[x] '@empty)] is an idiom once frequently used to copy the
list @i[x], but the @f[copy-list] function is more appropriate to this
task.
@Enddefun

@Defun[Fun {copy-list⎇, Args {@i[list]⎇]
This returns a list that is @f[equal] to @i[list], but not @f[eq].
Only the top level of list structure is copied; that is, @f[copy-list]
copies in the @i[cdr] direction but not in the @i[car] direction.
If the list is ``dotted,'' that is, @f[(cdr (last @i[list]))]
is a non-@nil atom, this will be true of the returned list also.
See also @Funref[copy-seq] and @Funref[copy-tree].
@Enddefun

@Defun[Fun {copy-alist⎇, Args {@i[list]⎇]
@f[copy-alist] is for copying association lists.  The top level of
list structure of @i[list] is copied, just as for @f[copy-list].
In addition, each element of @i[list] that is a cons is replaced
in the copy by a new cons with the same @i[car] and @i[cdr].
@Enddefun

@Defun[Fun {copy-tree⎇, Args {@i[object]⎇]
@f[copy-tree] is for copying trees of conses.
The argument @i[object] may be any @xlisp object.
If it is not a cons, it is returned; otherwise
the result is a new cons of the results of calling @f[copy-tree]
on the @i[car] and @i[cdr] of the argument.  In other words,
all conses in the tree are copied recursively, stopping
only when non-conses are encountered.
Circularities and the sharing of substructure are @i[not] preserved.

@Incompatibility{This function is called @f[copy] in @interlisp.⎇
@Enddefun

@Defun[Fun {revappend⎇, Args {@i[x] @i[y]⎇]
@f[(revappend @i[x] @i[y])] is exactly the same as 
@f[(append (reverse @i[x]) @i[y])] except that it is potentially more
efficient.  Both @i[x] and @i[y] should be lists.
The argument @i[x] is copied, not destroyed.
Compare this with @Funref[nreconc], which destroys its first argument.
@Enddefun

@Defun[Fun {nconc⎇, Args {@rest @i[lists]⎇]
@f[nconc] takes lists as arguments.  It returns a list that is the arguments
concatenated together.  The arguments are changed, rather than copied.
(Compare this with @Funref[append], which copies arguments rather than
destroying them.)
For example:
@lisp
(setq x '(a b c))
(setq y '(d e f))
(nconc x y) @EV (a b c d e f)
x @EV (a b c d e f)
@Endlisp
Note, in the example, that the value of @f[x] is now different,
since its last cons has been @f[rplacd]'d to the value of @f[y].
If one were then to evaluate @f[(nconc x y)] again,
it would yield a piece of ``circular'' list
structure, whose printed representation would be
@f[(a b c d e f d e f d e f ...)], repeating forever;
if the @Varref[print-circle] switch were non-@nil,
it would be printed as @f[(a b c . #1=(d e f . #1#))].
@Enddefun

@Defun[Fun {nreconc⎇, Args {@i[x] @i[y]⎇]
@f[(nreconc @i[x] @i[y])] is exactly the same as 
@f[(nconc (nreverse @i[x]) @i[y])] except that it is potentially more
efficient.  Both @i[x] and @i[y] should be lists.
The argument @i[x] is destroyed.
Compare this with @Funref[revappend].
@Enddefun


@Defmac[Fun {push⎇, Args {@i[item] @i[place]⎇]
The form @i[place] should be the name of a generalized variable
containing a list; @i[item] may refer to any @xlisp object.  The @i[item]
is consed onto the front of the list, and the augmented list is stored
back into @i[place] and returned.
The form @i[place] may be any form acceptable as a
generalized variable to @Macref[setf].  If the list held in @i[place] is
viewed as a push-down stack, then @f[push] pushes an element onto the top
of the stack.
For example:
@lisp
(setq x '(a (b c) d))
(push 5 (cadr x)) @EV (5 b c)  @r[and now] x @EV (a (5 b c) d)
@Endlisp
The effect of @f[(push @i[item] @i[place])]
is roughly equivalent to
@Lisp
(setf @i[place] (cons @i[item] @i[place]))
@Endlisp
except that the latter would evaluate any subforms of @i[place]
twice, while @f[push] takes care to evaluate them only once.
Moreover, for certain @i[place] forms @f[push] may be
significantly more efficient than the @f[setf] version.
@Enddefmac

@Defmac[Fun {pushnew⎇, Args {@i[item] @i[place]⎇, Keys {[test][test-not][key]⎇]
The form @i[place] should be the name of a generalized variable
containing a list; @i[item] may refer to any @xlisp object.  If the
@i[item] is not already a member of the list (as determined by
comparisons using the @Kwd[test] predicate, which defaults to @f[eql]),
then the @i[item] is consed onto the front of the list, and
the augmented list is stored back into @i[place] and returned; otherwise
the unaugmented list is returned.  The form @i[place] may be
any form acceptable as a generalized variable to @Macref[setf].  If the
list held in @i[place] is viewed as a set, then @f[pushnew] adjoins an
element to the set; see @Funref[adjoin].

The keyword arguments to @f[pushnew]
follow the conventions for the generic sequence
functions.  See chapter @Ref[KSEQUE].
In effect, these keywords are simply passed on to the @f[adjoin] function.

@f[pushnew] returns the new contents of the @i[place].
For example:
@lisp
(setq x '(a (b c) d))
(pushnew 5 (cadr x)) @EV (5 b c)   @r[and now] x @EV (a (5 b c) d)
(pushnew 'b (cadr x)) @EV (5 b c)  @r[and @f[x] is unchanged]
@Endlisp
The effect of
@lisp
(pushnew @i[item] @i[place] @Kwd[test] @i[p])
@endlisp
is roughly equivalent to
@Lisp
(setf @i[place] (adjoin @i[item] @i[place] @Kwd[test] @i[p]))
@Endlisp
except that the latter would evaluate any subforms of
@i[place] twice, while @f[pushnew] takes care to evaluate them only once.
Moreover, for certain @i[place] forms @f[pushnew] may be
significantly more efficient than the @f[setf] version.
@Enddefmac

@Defmac[Fun {pop⎇, Args {@i[place]⎇]
The form @i[place] should be the name of a generalized variable
containing a list.  The result of @f[pop] is the @f[car] of the contents
of @i[place], and as a side effect the @f[cdr] of the contents is stored
back into @i[place].  The form @i[place] may be any form acceptable as a
generalized variable to @Macref[setf].  If the list held in @i[place] is
viewed as a push-down stack, then @f[pop] pops an element from the top of
the stack and returns it.
For example:
@lisp
(setq stack '(a b c))
(pop stack) @EV a  @r[and now] stack @EV (b c)
@Endlisp
The effect of @f[(pop @i[place])] is roughly equivalent to
@Lisp
(prog1 (car @i[place]) (setf @i[place] (cdr @i[place])))
@Endlisp
except that the latter would evaluate any subforms of @i[place]
three times, while @f[pop] takes care to evaluate them only once.
Moreover, for certain @i[place] forms @f[pop] may be
significantly more efficient than the @f[setf] version.
@Enddefmac

@Defun[Fun {butlast⎇, Args {@i[list] @optional @i[n]⎇]
This creates and returns a list with the same elements as @i[list],
excepting the last @i[n] elements.
@i[n] defaults to 1.  The argument is not destroyed.
If the @i[list] has fewer than @i[n] elements, then @empty is returned.
For example:
@lisp
(butlast '(a b c d)) @EV (a b c)
(butlast '((a b) (c d))) @EV ((a b))
(butlast '(a)) @EV @empty
(butlast nil) @EV @empty
@Endlisp
The name is from the phrase ``all elements but the last.''
@Enddefun

@Defun[Fun {nbutlast⎇, Args {@i[list] @optional @i[n]⎇]
This is the destructive version of @f[butlast]; it changes the @i[cdr] of
the cons @i[n]+1 from the end of the @i[list] to @nil.  @i[n] defaults to 1.
If the @i[list] has fewer than @i[n] elements, then @f[nbutlast]
returns @empty, and the argument is not modified.  (Therefore
one normally writes @f[(setq a (nbutlast a))] rather than simply
@f[(nbutlast a)].)
For example:
@lisp
(setq foo '(a b c d))
(nbutlast foo) @EV (a b c)
foo @EV (a b c)
(nbutlast '(a)) @EV @empty
(nbutlast '@nil) @EV @empty
@Endlisp
@Enddefun


@Defun[Fun {ldiff⎇, Args {@i[list] @i[sublist]⎇]
@i[list] should be a list, and @i[sublist] should be a sublist
of @i[list], that is, one of the conses that make up @i[list].
@f[ldiff] (meaning ``list difference'') will return a new (freshly consed)
list, whose elements are those elements of @i[list] that appear before
@i[sublist].  If @i[sublist] is not a tail of @i[list]
(and in particular if @i[sublist] is @nil),
then a copy of the entire @i[list] is returned.
The argument @i[list] is not destroyed.
For example:
@lisp
(setq x '(a b c d e))
(setq y (cdddr x)) @EV (d e)
(ldiff x y) @EV (a b c)
@r[but]
(ldiff '(a b c d) '(c d)) @EV (a b c d)
@r[since the sublist was not @f[eq] to any part of the list.]
@Endlisp
@Enddefun


@Section[Alteration of List Structure]

The functions @f[rplaca] and @f[rplacd]
may be used to make alterations in already existing
list structure, that is, to change the @i[car] or @i[cdr] of an
existing cons.
One may also use @Macref[setf] in conjunction with @f[car] and @Funref[cdr].

The structure is not copied but is physically altered;
hence caution should be exercised when using these functions, as
strange side effects can occur if portions of list structure become
shared.
The @Funref[nconc], @Funref[nreverse], @Funref[nreconc],
and @Funref[nbutlast] functions, already
described,
have the same property, as do certain of the generic sequence
functions such as @Funref[delete].
However, they are normally not
used for this side effect; rather, the list-structure modification
is purely for efficiency, and compatible non-modifying functions
are provided.

@Defun[Fun {rplaca⎇, Args {@i[x] @i[y]⎇]
@f[(rplaca @i[x] @i[y])] changes the @i[car] of @i[x] to @i[y] and returns
(the modified) @i[x].  @i[x] must be a cons, but @i[y] may be any
@xLisp object.
For example:
@lisp
(setq g '(a b c))
(rplaca (cdr g) 'd) @EV (d c)
@r[Now] g @EV (a d c)
@Endlisp
@Enddefun

@Defun[Fun {rplacd⎇, Args {@i[x] @i[y]⎇]
@f[(rplacd @i[x] @i[y])] changes the @i[cdr] of @i[x] to @i[y] and returns
(the modified) @i[x].  @i[x] must be a cons, but @i[y] may be
any @xLisp object.
For example:
@lisp
(setq x '(a b c))
(rplacd x 'd) @EV (a . d)
@r[Now] x @EV (a . d)
@Endlisp
@Enddefun

@Section[Substitution of Expressions]

@Index[substitution]
A number of functions are provided for performing substitutions
within a tree.  All take a tree and a description
of old subexpressions to be replaced by new ones.
They come in non-destructive and destructive varieties
and specify substitution either by two arguments or by an association list.

The naming conventions for these functions and for their keyword
arguments generally follow the conventions for the generic sequence
functions.  See chapter @Ref[KSEQUE].

@Defun[Fun {subst⎇, Args {@i[new] @i[old] @i[tree]⎇, Keys {[test][test-not][key]⎇]
@Defun1[Fun {subst-if⎇, Args {@i[new] @i[test] @i[tree]⎇, Keys {[key]⎇]
@Defun1[Fun {subst-if-not⎇, Args {@i[new] @i[test] @i[tree]⎇, Keys {[key]⎇]
@f[(subst @i[new] @i[old] @i[tree])] makes a copy of @i[tree],
substituting @i[new] for every subtree or leaf of @i[tree]
(whether the subtree or leaf is a @i[car] or a @i[cdr] of its parent)
such that @i[old] and the subtree or leaf satisfy the test.  It
returns the modified copy of @i[tree].  The original @i[tree] is
unchanged, but the result tree may share with parts of the argument
@i[tree].
@Incompatibility{In @maclisp, @f[subst] is guaranteed @i[not] to share with
the @i[tree] argument, and the idiom @f[(subst @nil @nil x)] was
used to copy a tree @f[x].  In @clisp, the function @Funref[copy-tree] should
be used to copy a tree, as the @f[subst] idiom will not work.⎇
For example:
@lisp
(subst 'tempest 'hurricane
       '(shakespeare wrote (the hurricane)))
   @EV (shakespeare wrote (the tempest))
(subst 'foo '@nil '(shakespeare wrote (twelfth night)))
   @EV (shakespeare wrote (twelfth night . foo) . foo)
(subst '(a . cons) '(old . pair)
       '((old . spice) ((old . shoes) old . pair) (old . pair))
       @Kwd[test] #'equal)
   @EV ((old . spice) ((old . shoes) a . cons) (a . cons))
@Endlisp
This function is not destructive; that is, it does not change
the @i[car] or @i[cdr] of any already existing list structure.
One possible definition of @f[subst]:
@lisp
(defun subst (old new tree @rest x @key test test-not key)
  (cond ((satisfies-the-test old tree :test test
			     :test-not test-not :key key)
	 new)
	((atom tree) tree)
	(t (let ((a (apply #'subst old new (car tree) x))
		 (d (apply #'subst old new (cdr tree) x)))
	     (if (and (eql a (car tree))
		      (eql d (cdr tree)))
		 tree
		 (cons a d))))))
@endlisp
See also @Funref[substitute], which substitutes for top-level elements
of a sequence.
@Enddefun

@Defun[Fun {nsubst⎇, Args {@i[new] @i[old] @i[tree]⎇, Keys {[test][test-not][key]⎇]
@Defun1[Fun {nsubst-if⎇, Args {@i[new] @i[test] @i[tree]⎇, Keys {[key]⎇]
@Defun1[Fun {nsubst-if-not⎇, Args {@i[new] @i[test] @i[tree]⎇, Keys {[key]⎇]
@f[nsubst] is a destructive version of @f[subst].  The list structure of
@i[tree] is altered by destructively replacing with @i[new]
each leaf of the @i[tree] such that @i[old] and the leaf
satisfy the test.
@Enddefun

@Defun[Fun {sublis⎇, Args {@i[alist] @i[tree]⎇, Keys {[test][test-not][key]⎇]
@f[sublis] makes substitutions for objects in a tree
(a structure of conses).
The first argument to @f[sublis] is an association list.
@Index2[P {association list⎇, S {as a substitution table⎇]
The second argument is the tree in which
substitutions are to be made, as for @Funref[subst].
@f[sublis] looks at all subtrees and leaves of the tree;
if a subtree or leaf appears as a key in the association
list (that is, the key and the subtree or leaf satisfy the test),
it is replaced by the object it is associated
with.  This operation is non-destructive.  In effect, @f[sublis] can
perform several @f[subst] operations simultaneously.
For example:
@lisp
(sublis '((x . 100) (z . zprime))
        '(plus x (minus g z x p) 4 . x))
   @EV (plus 100 (minus g zprime 100 p) 4 . 100)

(sublis '(((+ x y) . (- x y)) ((- x y) . (+ x y)))
	'(* (/ (+ x y) (+ x p)) (- x y))
	:test #'equal)
   @EV (* (/ (- x y) (+ x p)) (+ x y))
@Endlisp
@Enddefun

@Defun[Fun {nsublis⎇, Args {@i[alist] @i[tree]⎇, Keys {[test][test-not][key]⎇]
@f[nsublis] is like @f[sublis] but destructively modifies the relevant
parts of the @i[tree].
@Enddefun

@Section[Using Lists as Sets]

@clisp includes functions that allow a list of items to be
treated as a @i[set].
@Index2[P {set⎇, S {list representation⎇]
There are functions to add, remove, and search for items in a list,
based on various criteria.
There are also set union, intersection, and difference functions.

The naming conventions for these functions and for their keyword
arguments generally follow the conventions for the generic sequence
functions.  See chapter @Ref[KSEQUE].

@Defun[Fun {member⎇, Args {@i[item] @i[list]⎇, Keys = {[test][test-not][key]⎇]
@Defun1[Fun {member-if⎇, Args {@i[predicate] @i[list]⎇, Keys = {[key]⎇]
@Defun1[Fun {member-if-not⎇, Args {@i[predicate] @i[list]⎇, Keys = {[key]⎇]
The @i[list] is searched for an element that satisfies the test.
If none is found, @false is returned;
otherwise, the tail of @i[list] beginning
with the first element that satisfied the test is returned.
The @i[list] is searched on the top level only. 
These functions are suitable for use as predicates.
For example:
@lisp
(member 'snerd '(a b c d)) @EV @false
(member-if #'numberp '(a #\Space 5/3 foo)) @EV (5/3 foo)
(member 'a '(g (a y) c a d e a f)) @EV (a d e a f)
@Endlisp
Note, in the last example,
that the value returned by @f[member] is @f[eq] to the portion of the list
beginning with @i[a].
Thus @f[rplaca] on the result of @f[member] may be used
to alter the found list element,
if a check is first made that @f[member] did not return @false.

See also @Funref[find] and @Funref[position].
@Incompatibility{In @maclisp, the @f[member] function uses
an @f[equal] comparison rather than @f[eql], which is the default
test for @f[member] in @clisp.  Where in @maclisp one would write
@f[(member x y)], in @clisp one must write @f[(member x y :test #'equal)]
to get a completely identical effect.  Similarly, one can get the
precise effect, and no more, of the @maclisp @f[(memq x y)]
by writing in @clisp @f[(member x y :test #'eq)].⎇
@Enddefun

@Defun[Fun {tailp⎇, Args {@i[sublist] @i[list]⎇]
This predicate is true if @i[sublist] is a sublist of @i[list] (i.e.,
one of the conses that makes up @i[list]); otherwise it is false.
Another way to look at this is that @f[tailp] is true if
@f[(nthcdr @i[n] @i[list])] is @i[sublist], for some value of @i[n].
See @Funref[ldiff].
@Enddefun

@Defun[Fun {adjoin⎇, Args {@i[item] @i[list]⎇, Keys = {[test][test-not][key]⎇]
@f[adjoin] is used to add an element to a set, provided that
it is not already a member.  The equality test defaults to @f[eql].
@Lisp
(adjoin @i[item] @i[list]) @EQ (if (member @i[item] @i[list]) @i[list] (cons @i[item] @i[list]))
@Endlisp
In general, the test may be any predicate; the @i[item] is added to the
list only if there is no element of the list that ``satisfies the test.''

@f[adjoin] deviates from the usual rules described in chapter @ref[KSEQUE]
for the treatment of arguments named @i[item] and @Kwd[key].
If a @Kwd[key] function is specified, it is applied to @i[item]
as well as to each element of the list.  The rationale is that
if the @i[item] is not yet in the list, it soon will be, and so
the test is more properly viewed as being between two elements
rather than between a separate @i[item] and an element.
@Lisp
(adjoin @i[item] @i[list] :key @i[fn])
  @EQ (if (member (@i[fn] @i[item]) @i[list] :key @i[fn]) @i[list] (cons @i[item] @i[list]))
@Endlisp
See @Macref[pushnew].
@Enddefun

@Defun[Fun {union⎇, Args {@i[list1] @i[list2]⎇, Keys = {[test][test-not][key]⎇]
@Defun1[Fun {nunion⎇, Args {@i[list1] @i[list2]⎇, Keys = {[test][test-not][key]⎇]
@f[union] takes two lists and returns a new list containing
everything that is an element of either of the @i[lists].
If there is a duplication between two lists,
only one of the duplicate instances will be in the result.
If either of the arguments has duplicate entries within it,
the redundant entries
may or may not appear in the result.
For example:
@lisp
(union '(a b c) '(f a d))
  @EV (a b c f d) @r[or] (b c f a d) @r[or] (d f a b c) @r[or] ...

(union '((x 5) (y 6)) '((z 2) (x 4)) :key #'car)
  @EV ((x 5) (y 6) (z 2)) @r[or] ((x 4) (y 6) (z 2)) @r[or] ...
@Endlisp

There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be @f[eq] to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the union operation may be
described as follows.  For all possible ordered pairs consisting of one
element from @i[list1] and one element from @i[list2], the test is used
to determine whether they ``match.''  For every matching pair, at least
one of the two elements of the pair will be in the result.  Moreover, any
element from either list that matches no element of the other will appear
in the result.  All this is very general, but probably not particularly
useful unless the test is an equivalence relation.

The @Kwd[test-not] argument can be useful when the test function
is the logical negation of an equivalence test.  A good example
of this is the function @Funref[mismatch], which is logically inverted
so that possibly useful information can be returned if the arguments do not
match.  This additional ``useful information'' is discarded in the following
example; @f[mismatch] is used purely as a predicate.
@lisp
(union '(#(a b) #(5 0 6) #(f 3))
       '(#(5 0 6) (a b) #(g h))
       :test-not
       #'mismatch)
   @EV (#(a b) #(5 0 6) #(f 3) #(g h))	;@r[One possible result]
   @EV ((a b) #(f 3) #(5 0 6) #(g h))	;@r[Another possible result]
@endlisp
Using @f[@Kwd[test-not] #'mismatch] differs from using
@f[@Kwd[test] #'equalp], for example, because @f[mismatch]
will determine that @f[#(a b)] and @f[(a b)] are the same,
while @Funref[equalp] would regard them as not the same.

@f[nunion] is the destructive version of @f[union].
It performs the same operation but may destroy the argument lists,
using their cells to construct the result.
@Enddefun

@Defun[Fun {intersection⎇, Args {@i[list1] @i[list2]⎇, Keys = {[test][test-not][key]⎇]
@Defun1[Fun {nintersection⎇, Args {@i[list1] @i[list2]⎇, Keys = {[test][test-not][key]⎇]
@f[intersection] takes two lists and returns a new list containing
everything that is an element of both argument lists.
If either list has duplicate entries, the redundant entries
may or may not appear in the result.
For example:
@lisp
(intersection '(a b c) '(f a d)) @EV (a)
@Endlisp
There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be @f[eq] to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the intersection operation
may be described as follows.  For all possible ordered pairs consisting of
one element from @i[list1] and one element from @i[list2], the test is
used to determine whether they ``match.''  For every matching pair,
exactly one of the two elements of the pair will be put in the result.
No element from either list appears in the result that does not match
an element from the other list.
All this is very general, but probably
not particularly useful unless the test is an equivalence relation.

@f[nintersection] is the destructive version of @f[intersection].
It performs the same operation, but may destroy @i[list1]
using its cells to construct the result.  (The argument @i[list2]
is @i[not] destroyed.)
@Enddefun

@Defun[Fun {set-difference⎇, Args {@i[list1] @i[list2]⎇, Keys = {[test][test-not][key]⎇]
@Defun1[Fun {nset-difference⎇, Args {@i[list1] @i[list2]⎇, Keys = {[test][test-not][key]⎇]
@f[set-difference] returns a list of elements of @i[list1]
that do not appear in @i[list2].  This operation is
not destructive.

There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be @f[eq] to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the set difference operation
may be described as follows.  For all possible ordered pairs consisting of
one element from @i[list1] and one element from @i[list2], the test is
used to determine whether they ``match.''  An element of @i[list1]
appears in the result if and only if it does not match any element
of @i[list2].  This is very general and permits interesting applications.
For example, one can remove from a list of strings all those strings
containing one of a given list characters:
@lisp
;; Remove all flavor names that contain "c" or "w".
(set-difference '("strawberry" "chocolate" "banana"
		  "lemon" "pistachio" "rhubarb")
		'(#\c #\w)
		:test
		#'(lambda (s c) (find c s)))
   @EV ("banana" "rhubarb" "lemon")	;@r[One possible ordering.]
@endlisp

@f[nset-difference] is the destructive version of @f[set-difference].
This operation may destroy @i[list1].

@Incompatibility{An approximately equivalent @interlisp function
is @f[ldifference].⎇
@Enddefun

@Defun[Fun {set-exclusive-or⎇, Args {@i[list1] @i[list2]⎇, Keys = {[test][test-not][key]⎇]
@Defun1[Fun {nset-exclusive-or⎇, Args {@i[list1] @i[list2]⎇, Keys = {[test][test-not][key]⎇]
@f[set-exclusive-or] returns a list of elements that appear
in exactly one of @i[list1] and @i[list2].
This operation is not destructive.

There is no guarantee that the order of elements in the result will
reflect the ordering of the arguments in any particular way.
The implementation is therefore free to use any of a variety of strategies.
The result list may share cells with, or be @f[eq] to, either of the arguments
if appropriate.

In general, the test may be any predicate, and the set-exclusive-or operation
may be described as follows.  For all possible ordered pairs consisting of
one element from @i[list1] and one element from @i[list2], the test is
used to determine whether they ``match.''  The result contains precisely
those elements of @i[list1] and @i[list2] that appear in no matching pair.

@f[nset-exclusive-or] is the destructive version of @f[set-exclusive-or].
Both lists may be destroyed in producing the result.
@Enddefun

@Defun[Fun {subsetp⎇, Args {@i[list1] @i[list2]⎇, Keys = {[test][test-not][key]⎇]
@f[subsetp] is a predicate that is true if every element of @i[list1]
appears in (``matches'' some element of) @i[list2], and false otherwise.
@Enddefun


@Section[Association Lists]

An @Def[association list], or @Def[a-list], is a data structure
used very frequently in @xlisp.  An a-list is a list of pairs (conses);
each pair is an association.  The @i[car] of a pair is called the @i[key],
and the @i[cdr] is called the @i[datum].

An advantage of the a-list representation is that an a-list can be
incrementally augmented simply by adding new entries to the front.
Moreover, because the searching function @Funref[assoc] searches the
a-list in order, new entries can ``shadow'' old entries.  If an a-list is
viewed as a mapping from keys to data, then the mapping can be not only
augmented but also altered in a non-destructive manner by adding new
entries to the front of the a-list.

Sometimes an a-list represents a bijective mapping, and it is desirable
to retrieve a key given a datum.  For this purpose, the ``reverse'' searching
function @Funref[rassoc] is provided.  Other variants of a-list searches
can be constructed using the function @Funref[find] or @Funref[member].

It is permissible to let @false be an element of an a-list in place of
a pair.  Such an element is not considered to be a pair but is simply
passed over when the a-list is searched by @Funref[assoc].

@Defun[Fun {acons⎇, Args {@i[key] @i[datum] @i[a-list]⎇]
@f[acons] constructs a new association list by adding the pair
@f[(@i[key] . @i[datum])] to the old @i[a-list].
@Lisp
(acons x y a) @EQ (cons (cons x y) a)
@Endlisp
@Enddefun

@Defun[Fun {pairlis⎇, Args {@i[keys] @i[data] @optional @i[a-list]⎇]
@f[pairlis] takes two lists and makes an association list that associates
elements of the first list to corresponding elements of the second
list.  It is an error if the two lists @i[keys] and @i[data] are not of
the same length.  If the optional argument @i[a-list] is provided, then the
new pairs are added to the front of it.

The new pairs may appear in the resulting a-list in any order;
in particular, either forward or backward order is permitted.
Therefore the result of the call
@Lisp
(pairlis '(one two) '(1 2) '((three . 3) (four . 19)))
@endlisp
might be
@lisp
((one . 1) (two . 2) (three . 3) (four . 19))
@endlisp
but could equally well be
@lisp
((two . 2) (one . 1) (three . 3) (four . 19))
@Endlisp
@Enddefun

@Defun[Fun {assoc⎇, Args {@i[item] @i[a-list]⎇, Keys = {[test][test-not]⎇]
@Defun1[Fun {assoc-if⎇, Args {@i[predicate] @i[a-list]⎇]
@Defun1[Fun {assoc-if-not⎇, Args {@i[predicate] @i[a-list]⎇]
Each of these searches the association list
@i[a-list].  The value is the first pair in the a-list such that
the @i[car] of the pair satisfies the test, or @false if there is
no such pair in the a-list.
For example:
@lisp
(assoc 'r '((a . b) (c . d) (r . x) (s . y) (r . z)))
	@EV  (r . x)
(assoc 'goo '((foo . bar) (zoo . goo))) @EV @false
(assoc '2 '((1 a b c) (2 b c d) (-7 x y z))) @EV (2 b c d)
@Endlisp
It is possible to @f[rplacd] the result of @f[assoc] @i[provided]
that it is not @false,
in order to ``update'' the ``table'' that was @f[assoc]'s second argument.
(However, it is often better to update an a-list by adding new pairs
to the front, rather than altering old pairs.)
For example:
@lisp
(setq values '((x . 100) (y . 200) (z . 50)))
(assoc 'y values) @EV (y . 200)
(rplacd (assoc 'y values) 201)
(assoc 'y values) @EV (y . 201) @r[now]
@Endlisp
A typical trick is to say
@f[(cdr (assoc x y))].
Because the @i[cdr] of @false is guaranteed to be @false,
this yields @false if no pair is found @i[or] if a pair is
found whose @i[cdr] is @false.  This is useful if @false serves
its usual role as a ``default value.''

The two expressions
@Lisp
(assoc @i[item] @i[list] :test @i[fn])
@endlisp
and
@lisp
(find @i[item] @i[list] :test @i[fn] :key #'car)
@Endlisp
are equivalent in meaning with one important exception:
if @nil appears in the a-list in place of a pair,
and the @i[item] being searched for is @nil,
@f[find] will blithely compute the @i[car] of the @nil in the a-list,
find that it is equal to the @i[item], and return @nil,
whereas @f[assoc] will ignore the @nil in the a-list and continue
to search for an actual pair (cons) whose @i[car] is @nil.
See @Funref[find] and @Funref[position].

@Incompatibility{In @maclisp, the @f[assoc] function uses
an @f[equal] comparison rather than @f[eql], which is the default
test for @f[assoc] in @clisp.  Where in @maclisp one would write
@f[(assoc x y)], in @clisp one must write @f[(assoc x y :test #'equal)]
to get the completely identical effect.  Similarly, one can get the
precise effect, and no more, of the @maclisp @f[(assq x y)]
by writing in @clisp @f[(assoc x y :test #'eq)].

In @interlisp, @f[assoc] uses an @f[eq] test, and @f[sassoc]
uses an @interlisp @f[equal] test.⎇
@Enddefun

@Defun[Fun {rassoc⎇, Args {@i[item] @i[a-list]⎇, Keys {[test][test-not]⎇]
@Defun1[Fun {rassoc-if⎇, Args {@i[predicate] @i[a-list]⎇]
@Defun1[Fun {rassoc-if-not⎇, Args {@i[predicate] @i[a-list]⎇]
@f[rassoc] is the reverse form of @f[assoc]; it searches for
a pair whose @i[cdr] satisfies the test, rather than the @i[car].
If the @i[a-list] is considered to be a mapping, then @f[rassoc]
treats the @i[a-list] as representing the inverse mapping.
For example:
@lisp
(rassoc 'a '((a . b) (b . c) (c . a) (z . a))) @EV (c . a)
@Endlisp

The expressions
@Lisp
(rassoc @i[item] @i[list] :test @i[fn])
@endlisp
and
@lisp
(find @i[item] @i[list] :test @i[fn] :key #'cdr)
@Endlisp
are equivalent in meaning, except when the @i[item] is @nil
and @nil appears in place of a pair in the a-list.  See the discussion
of the function @Funref[assoc].
@Enddefun